#include<iostream>

using namespace std;
typedef long long ll;

int get_phi(int n)
{
	if(n==1) return 0;
	int ret=n;
	for(int i=2;i<=n/i;i++)
	{
		if(n%i==0)
		{
			ret=ret/i*(i-1);
			while(n%i==0)
			{
				n/=i;
			}
		}
	}
	if(n>1) ret=ret/n*(n-1);
	return ret;
}

int get_b(string s,int m)
{
	int ret=0;
	bool flag=false;
	for(int i=0;i<s.size();i++)
	{
		ret=ret*10+(s[i]-'0');
		if(ret>m)
		{
			ret=ret%m;
			flag=true;
		}
	}

	if(flag) ret+=m;
	return ret;
}

ll qpow(ll a,ll b,ll c)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%c;
		b>>=1;
		a=a*a%c;
	}
	return ret;
}

int main()
{
	int a;cin>>a;
	int m;cin>>m;
	string s; cin>>s;
	
	int phi=get_phi(m);
	int b=get_b(s,phi);

	cout<<qpow(a,b,m)<<endl;

}